\begin{dis}{\LARGE\scshape Conjunto ACOTADO} \normalfont
\especif

\\ \hspace*{2em}Se usara el siguiente TAD

\begin{tadx}{Conjunto Acotado}{}
\\
\usa{BOOL, NAT}
\exporta{generadores, observadores, $\#$, $\emptyset$?, $\bigcup$}
\generos{conjAcotado}

\igualobs{$\\$ ($\forall$ c, c' : ConjAcotado($\alpha$))(c $\igobs$ c' $\Leftrightarrow$ (limite(c) $\igobs$ limite(c')) $\\$ $\wedge$ ($\forall$ elem : $\alpha$) (elem $\in$ c $\igobs$ elem $\in$ c'))}

\observadores
\func{$\in$}{$\alpha$, conjAcotado($\alpha$)}{bool}{}
\func{limite}{conjAcotado($\alpha$)}{nat}{}

\generadores
\func{$\emptyset$}{nat/tamanio}{conjAcotado($\alpha$)}{(taminio $>$ 0)}
\func{Ag}{$\alpha$/elem,conjAcotado($\alpha$)/c}{conjAcotado($\alpha$)}{($\#$(c) $<$ limite(c)) $\wedge$ $\neg$(elem $\in$ c)}

\otrasops
\func{$\#$}{conjAcotado($\alpha$))}{nat}{}
\func{dameUno}{conjAcotado($\alpha$)/c}{$\alpha$}{($\#$(c) $>$ 0)}
\func{sinUno}{conjAcotado($\alpha$)/c}{conjAcotado($\alpha$)}{($\#$(c) $>$ 0)}
\func{$\emptyset$?}{conjAcotado($\alpha$)}{bool}{}
\func{$\puntito$ - $\puntito$}{conjAcotado($\alpha$), conjAcotado($\alpha$)}{conjAcotado($\alpha$)}{}
\func{$\bigcup$}{conjAcotado($\alpha$)/c$_1$, conjAcotado($\alpha$)/c$_2$}{conjAcotado($\alpha$)}{}

\axiomas{$\forall$ c,d : conjAcotado($\alpha$), $\forall$ a,b : $\alpha$}
\axioma{a $\in$ $\emptyset$(tamanio)}{false}
\axioma{a $\in$ Ag(elem, c)}{(a = elem) $\vee$ (a $\in$ c)}
\\
\axioma{limite($\emptyset$(tamanio))}{tamanio}
\axioma{limite(Ag(elem, c))}{limite(c)}
\\\textcolor{red}
\axioma{$\#$($\emptyset$(tamanio))}{0}
\axioma{$\#$(Ag(elem, c))}{1+$\#$(c-{a})}
\\
\axioma{dameUno(c) $\in$ c}{true}
\axioma{sinUno(c)}{c - {dameUno(c)}}
\axioma{$\emptyset$?(c)}{($\#$(c) = 0)}
\\
\axioma{$\emptyset$(tamanio)-d}{$\emptyset$(tamanio)}
\axioma{Ag(elem, c)-d}{if (elem $\in$ d) then c-d else Ag(elem, c-d) fi}
\\
\axioma{c$_1$ $\bigcup$ c$_2$}{if ($\emptyset$?(c$_1$)) then $\\ \hspace*{1em}$ if ($\emptyset$?(c$_2$)) then $\\ \hspace*{2em}$ $\emptyset$(limite(c$_1$) + limite(c$_2$)) $\\ \hspace*{1em}$ else $\\ \hspace*{2em}$ Ag(dameUno(c$_2$), c$_1$ $\bigcup$ sinUno(c$_2$)) $\\ \hspace*{1em}$ fi $\\$ else $\\ \hspace*{1em}$ Ag(dameUno(c$_1$), sinUno(c$_1$) $\bigcup$ c$_2$) $\\$ fi}

\end{tadx}


\aspectos
\serviciosexp
\orden{iVacio}{O(n)}
\orden{iAg}{O(log(cantElementos))}
\orden{iSinUno}{O(log(cantElementos))}
\orden{iDameUno}{O(1)}
\orden{\#}{O(1)}
\orden{\emptyset?}{O(1)}
\orden{\in}{O(cantElementos)}
\orden{<-}{O(cantEle\textcolor{red}mentos)} 
\orden{\bigcup}{O(k + log (k +j) * j)}

Donde: 
\\ \hspace*{2em}$cantElementos$ representa la cantidad de elementos que tiene ese conjunto.
\\ \hspace*{2em}$k$ es el limite del primer conjunto
\\ \hspace*{2em}$j$ es el limite del segundo conjunto
\\ Todas las operaciones se hacen por referencia salvo la asignacion ($<$-), que se hace por copia\\

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\interfaz
\interface{Conjunto Acotado}

%\seexplica{Conjunto Acotado}
\usa{\scshape Bool, Nat}\normalfont
\exporta{iVacio, iAg, iSinUno, iDameUno }
\genero{ConjAcotado(\alpha)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\operaciones
\hspace*{3em} \textcolor{red}{--------------------------------------------------------------------} \\
\hspace*{1em} \begin{funcion}{\emptyset}{in \, tamanio : nat}{c :conjAcotado(\alpha)}{}{}
  \precond{tamanio > 0}
  \poscond{\emptyset?(\widehat{c}) \equiv True}
\end{funcion}

\hspace*{1em} \textcolor{red}{--------------------------------------------------------------------} \\
\hspace*{1em} \begin{funcion}{Ag}{in \, elem : \alpha, inout \, c : conjAcotado(\alpha)}{}{}
  \precond{\widehat{c} \igobs c$_0$}
  \poscond{\widehat{c} \igobs Ag(\widehat{elem}, c_0)}
\end{funcion} 

\hspace*{1em} \textcolor{red}{--------------------------------------------------------------------} \\
\hspace*{1em} \begin{funcion}{sinUno}{inout c : conjAcotado(\alpha}{}{}
   \precond{\widehat{c} \igobs c$_0$ \wedge \neg \emptyset?\widehat{c}}
   \poscond{\widehat{c} \igobs sinUno(c$_0$)}
\end{funcion} 

\hspace*{1em} \textcolor{red}{--------------------------------------------------------------------} \\
\hspace*{1em} \begin{funcion}{dameUno}{inout c : conjAcotado(\alpha)}{res : \alpha}{}
   \precond{\widehat{c} \igobs c$_0$ \wedge \neg \emptyset?\widehat{c}}
   \poscond{\widehat{res} \igobs dameUno(c$_0$) \wedge \widehat{c} \igobs c$_0$} 
\end{funcion} 

\hspace*{1em} \textcolor{red}{--------------------------------------------------------------------} \\
\hspace*{1em} \begin{funcion}{\in}{in \, elem : \alpha, in \, c : conjAcotado(\alpha)}{res : bool}{}
   \precond{true}
   \poscond{\widehat{res} \igobs (elem \in \widehat{c}}
\end{funcion} 

\hspace*{1em} \textcolor{red}{--------------------------------------------------------------------} \\
\hspace*{1em} \begin{funcion}{\#}{in \, c : conjAcotado(\alpha}{n: Nat}{}
   \precond{true}
   \poscond{\widehat{n} \igobs \#(\widehat{c})}
\end{funcion}

\hspace*{1em} \textcolor{red}{--------------------------------------------------------------------} \\
\hspace*{1em} \begin{funcion}{\emptyset?}{in \, c : conjAcotado(\alpha)}{res : bool}{}
   \precond{true}
   \poscond{\widehat{res} \igobs \emptyset?(\widehat{c})}
\end{funcion}
\hspace*{1em} \textcolor{red}{--------------------------------------------------------------------} \\
\hspace*{1em} \begin{funcion}{$<$-}{in \, c : conjAcotado(\alpha)}{res : conjAcotado(\alpha)}{}
   \precond{true}
   \poscond{\widehat{res} \igobs (\widehat{c})}
\end{funcion}
\hspace*{1em} \textcolor{red}{--------------------------------------------------------------------} \\
\hspace*{1em} \begin{funcion}{\bigcup}{in \, c_1 : conjAcotado(\alpha), in \, c_2 : conjAcotado(\alpha)}{res : conjAcotado(\alpha)}{}
   \precond{true}
   \poscond{\widehat{res} \igobs (\widehat{c$_1$} \bigcup \widehat{c$_2$})}
\end{funcion}

\intfin

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pautas

\estructura
\\\hspace*{2em} conjAcotado($\alpha$) se representa con \textbf{strConj}
\\\hspace*{2em}donde \textbf{strConj} es $<$ array: ArregloDimensionable($\alpha$), ultimaPosUsada : nat $>$

\invariante
\\
\\
\hspace*{2em} \textbf{Informalmente:} 
\\ \hspace*{2em} 1) No hay elementos repetidos en el arreglo 
\\ \hspace*{2em} 2) El arreglo cumple con el invariante de heap, es decir
\\ \hspace*{4em} a) Se empieza a llenar desde la ``izquierda``
\\ \hspace*{4em} b) El padre el menor que el hijo de la derecha y que el de la izquierda
\\ \hspace*{2em} 3) ultimaPosUsada indica lo siguiente:
\\ \hspace*{4em} i) Si es cero, entonces ninguna posicion delcantidad  arreglo fue definida
\\ \hspace*{4em} ii) Si esta entre cero y el tama~no del arreglo, entonces las posiciones entre 0 y ultimaPosUsada-1 (inclusive) estan definidas.
\\ \hspace*{4em} iii) Si es el tama~no del arreglo, entonces todo el arreglo esta definido
 ultima posicion definida del arreglo. Si apunta a una posicion invalida del arreglo, entonces el arreglo esta totalmente definido. Si ultimaPosUsada es cero, entonces indica que el arreglo esta vacio. 
\\
\\
\hspace*{1em} Rep: \widehat{strConjA} \longrightarrow Boolean \\
\hspace*{1em} ($\forall$ s : strConj) Rep(s) $\equiv$ 
\\ \hspace*{1em} (($\forall$ elem :$\alpha$) (esta?(s.array, elem, 0) $\Longrightarrow_L$ cantRep(s.array, elem, 0) = 1)) $\wedge$ 
\\ \hspace*{1em} (ordenado(s.array, 0)) $\wedge$ 
\\ \hspace*{1em} completadaDesdeLaIzquierda(s.array,0) $\wedge$
\\ \hspace*{1em} ((s.ultimaPosUsada = 0)$\Leftrightarrow$ ningunoEstaDefinido(s.array, s.ultimaPosicion)) $\wedge$
\\ \hspace*{1em} (((s.ultimaPosUsada $>$ 0) $\wedge$ (s.ultimaPosUsada $<$ tam(s.array))) $\Leftrightarrow$
\\ \hspace*{5em} ningunoEstaDefinido(s.array, s.ultimaPosicion) $\wedge$ todosEstanDefinidos(s.array, 0, s.ultimaPosicion))
\\ \hspace*{1em} ((s.ultimaPosUsada = tam(s.array))$\Leftrightarrow$ todosEstanDefinidos(s.array, s.ultimaPosicion-1))
\\
\\
\textbf{Funciones auxiliares:}
\\
\\
\hspace*{1em} esta?(in \, a : ArregloDimensionable($\alpha$), in \, elem : $\alpha$, in \, i : nat) $\longrightarrow$ bool 
\\ \hspace*{1em} esta?(a, elem, i) = if (i = tam(a)) then $\\ \hspace*{10em}$ false $\\ \hspace*{8em}$ else $\\ \hspace*{10em}$ if (definido?(a,i)) then $\\ \hspace*{12em}$ esta?(a, elem, e+1) $\\ \hspace*{10em}$ else $\\ \hspace*{12em}$ (a[i] == elem) $\vee$ esta?(a, elem, i+1) $\\ \hspace*{10em}$ fi $\\ \hspace*{8em}$ fi
\\
\\
\hspace*{1em} cantRep(in \, a : ArregloDimensionable($\alpha$), in \, elem : $\alpha$, in \, i : nat) $\longrightarrow$ nat
\\ \hspace*{1em} cantRep(a, elem, i) = if (i = tam(a)) then $\\ \hspace*{10em}$ 0 $\\ \hspace*{8em}$ else $\\ \hspace*{10em}$ if (definido?(a,i) then $\\ \hspace*{12em}$ if (a[i] = elem) then 1 else 0 fi + cantRep(a, elem, i+1) $\\ \hspace*{10em}$ else $\\ \hspace*{12em}$ cantRep(a, elem, i+1) $\\ \hspace*{10em}$ fi $\\ \hspace*{8em}$ fi
\\
\\ 
\hspace*{1em} ordenado (in \, a : ArregloDimensionable($\alpha$), in \, i : nat) $\longrightarrow$ bool 
\\ \hspace*{1em} ordenado(a,i) $\equiv$ if (i = tam(a)) then $\\ \hspace*{10em}$ true $\\ \hspace*{8em}$ else $\\ \hspace*{10em}$ if (definido?(a[i])) then $\\ \hspace*{12em}$ if (definido?(a,2*i+1)) $\\ \hspace*{14em}$  if definido?(a, 2*i+2)) then $\\ \hspace*{16em}$ (a[i] $\leq$ a[2*i+1]) $\wedge$ (a[i] $\leq$ a[2*i+2]) $\wedge$ (ordenado(a+i1)) $\\ \hspace*{14em}$ else $\\ \hspace*{16em}$ (a[i] $\leq$ a[2*i+1]) $\wedge$ ordenado(a, i+1) $\\ \hspace*{14em}$ fi $\\ \hspace*{12em}$ else $\\ \hspace*{14em}$ if definido?(a, 2*i+2)) then $\\ \hspace*{16em}$ (a[i] $\leq$ a[2*i+2]) $\wedge$ (ordenado(a+i1)) $\\ \hspace*{14em}$ else $\\ \hspace*{16em}$ ordenado(a, i+1) $\\ \hspace*{14em}$ fi $\\ \hspace*{12em}$ fi $\\ \hspace*{10em}$ else $\\ \hspace*{12em}$ true $\\ \hspace*{8em}$ fi
\\
\\
\hspace*{1em} completadaDesdeLaIzquierda (in \, a : arregloDimensionable($\alpha$), in \, i : nat) $\longrightarrow$ bool
\\ \hspace*{1em} completadaDesdeLaIzquierda(a,i) $\equiv$ if (i = tam(a)) then $\\ \hspace*{10em}$ true $\\ \hspace*{8em}$ else $\\ \hspace*{10em}$ if (definido?(a,i)) then $\\ \hspace*{12em}$ if (definido?(a, 2*i+1)) then $\\ \hspace*{14em}$ completadaDesdeLaIzquierda(a, 2*i+1) $\wedge$ completadaDesdeLaIzquierda(a, 2*i+2) $\\ \hspace*{12em}$ else $\\ \hspace*{14em}$ $\neg$definido?(a, 2*i+2) $\wedge$completadaDesdeLaIzquierda(a, 2*i+1) $\\ \hspace*{12em}$ fi $\\ \hspace*{10em}$ else $\\ \hspace*{12em}$ true $\\ \hspace*{10em}$ fi $\\ \hspace*{8em}$ fi
\\
\\
\hspace*{1em} ningunoEstaDefinido (in \, a : arregloDimensionable($\alpha$), in \, i : nat) $\longrightarrow$ bool
\\ \hspace*{1em} ningunoEstaDefinido(a,i) $\equiv$ if (i = tam(a)) then $\\ \hspace*{10em}$ true $\\ \hspace*{8em}$ else $\\ \hspace*{10em}$ if (definido?(a,i)) then $\\ \hspace*{12em}$ false $\\ \hspace*{10em}$ else $\\ \hspace*{12em}$ ningunoEstaDefinido(a,i+1) \\ \hspace*{10em}fi $\\   \hspace*{8em}$ fi
\\
\\
\hspace*{1em} todosEstanDefinidos( in \, a : arregloDimensionable, in \, i: nat, in ultimaPos : nat) $\longrightarrow$ bool
\\ \hspace*{1em} todosEstanDefinidos(a, i, ultimaPos) $\equiv$ 
if (i = ultimaPos-1) then $\\ \hspace*{10em}$ definido?(a, i) $\\ \hspace*{8em}$ else $\\ \hspace*{10em}$ definido?(a,i) $\wedge$ todosEstasDefinidos(a,i+1, ultimaPos) $\\ \hspace*{8em}$ fi
\\
\\
\funcabs 
\\ \hspace*{1em} Abs: $\widehat{strConj} \, $s$ \longrightarrow$ Conj($\alpha$)   \hspace*{11em} (Rep(s))\\
\hspace*{3em} ($\forall$ s:strConj) Abs(s) $\equiv$ c : conj($\alpha$)/ \\
\hspace*{4em} (($\forall$ elem: $\alpha$) elem $\in$ c \, $\igobs$ \, esta?(s.array, elem, 0)) $\wedge$ limite(c) $\igobs$ tam(s.array)

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\algoritmos 
\hspace*{1em} \textcolor{red}{----------------------------------------} \\
\hspace*{1em} i$\emptyset$ (in \, tamanio : nat) $\longrightarrow $ c :conjAcotado($\alpha$)
	\begin{verbatim}
	{
          var
                    i : nat
          c.array <- crearArreglo(tamanio)
          c.ultimaPosUsada <- 0
          i <- 0
          //lleno el arreglo de posiciones no definidas
          while (i < tamanio) {
                    c.array[1] <- nill
          }
	}
	\end{verbatim} 
\hspace*{1em} \textcolor{red}{----------------------------------------} \\
\hspace*{1em}	iAg (in \, elem :$\alpha$, inout c \,: conjAcotado($\alpha$))
	\begin{verbatim}
	{
          var
               indice : int
               noTermine : bComo en el cicloool
               padre : nat	
\end{verbatim}
\hspace*{7em}  elemAux :  $\alpha$ \begin{verbatim}
          a[c.ultimaPosUsada] <- elem
          indice <- c.ultimaPosUsada
          noTermine <- true
          while (indice > 0 && noTermine) {
               //primero veo quien seria el padre de este elemento
               if (indice % 2 == 0) {
                    //en este caso estoy parado sobre un nodo derecho
                    padre <- (indice -2) /2
                } else {
                    //en este caso estoy parado sobre un nodo izquierdo
                    padre <- (indice -1) /2
               }
               //ahora veo si intercambio los valores
               if (a[indice] < a[padre]) {
                    //entonces tengo que intercambiar los valores
                    elemAux <- a[indice]
                    a[indice] <- a[padre]
                    a[padre] <- a[indice]
                } else {
                    //sino iComo en el ciclontercambio ese dato, entonces no termino de hacer el while
                    noTermine <- false
               }
               //actualizo el valor del indice
               indice <- padre
          }
          s.ultimaPosUsada++	
	}
	\end{verbatim}
\hspace*{1em} \textcolor{red}{----------------------------------------} \\
\hspace*{1em} i$\in$ (in \, elem :$\alpha$, in \, c :conjAcotado($\alpha$)) $\longrightarrow$ res :bool
	\begin{verbatim}
	{
          var 
               i : nat
               noTermine : bool
          noTermine <- true
          i <- 0
          rest_value <- fa5.5lse
          //busco en todo el arreglo, en donde esta definido ese valor
          while (i < c.ultimoDefinido && noTermine) {
               if (c.array[i] = elem) {
                    res <- true
                    noTermine <- false
               }
               else {
                    i++res.ultimaPosUsada <- c2.ultiaPosUsada + c1.ultimaPosUsada
               }	
          }
	}
	\end{verbatim}
\hspace*{1em} \textcolor{red}{----------------------------------------} \\
\hspace*{1em} $\emptyset$? (in c :conjAcotado($\alpha$)) $\longrightarrow$ res :bool
	\begin{verbatim}
	{
        res <- (c.ultimaPosUsada == 0) 
	}
	\end{verbatim} 
\hspace*{1em} \textcolor{red}{----------------------------------------} \\
\hspace*{1em} idameUno (in c :conjAcotado($\alpha$))$\longrightarrow$ elem : $\alpha$
	\begin{verbatim}
	{
          elem <- c.a[0]
	}
	\end{verbatim} 
\hspace*{1em} \textcolor{red}{----------------------------------------} \\
\hspace*{1em} iSinUno (inout c :conjAcotado($\alpha$))
	\begin{verbatim}
	{
          var
               i : nat 
               noTermine : bool
               soloEstaDefinidoElHijoIzq : bool
               estanDefinidosLosDosHijos : bool
\end{verbatim}
\hspace*{7em}  elementoAux :  $\alpha$ \begin{verbatim}

          //primero subo el ultimo valor a la primer posicion,
          c.array[0] <- c.array[c.ultimaPosUsada-1] 
          borrar(c.array, c.ultimaPosUsada-1)
          //cambio el numero de valores que tengo definidos en el arreglo
          c.ultimaPosUsada <- c.ultimaPosUsada-1
          i <- 0
          noTermine <- true
          while (noTermine) {
               //me fijo si tiene los dos hijos definidos la posicion actual.
               soloEstaDefinidoElHijoIzq = definido?(a, 2*i+1)
               estanDefinidosLosDosHijos = soloEstaDefinidoElHijoIzq && definido?(a, 2*1+2)	

               //Si tiene los dos hijos definidos, me fijo por cual reemplazar
               if (estanDefinidosLosDosHijos) {
                    //me fijo si la raiz del hijo der es menor que la raiz actual, y a su vez que la raiz 
                    //del hijo izq es menor que la raiz del hijo der
                    if (c.array[2*i+2] < c.array[i] && c.array[2*i+2] < c.array[2*i+1] ) {
                         elementoAux <- c.array[2*i+2]
                         c.array[2*i+2] <- c.array[i]
                         c.array[i] <- elementoAux
                         i <- 2*i+2
                    }\begin{document}
                    //me fijo si la raiz del hijo izq es menor que la raiz actual, y a su vez que la raiz 
                    //del hijo der es menor que la raiz del hijo izq 
                    else if (c.array[2*i+1] < c.array[i] && c.array[2*i+1] < c.array[2*i+2]) {
                         elementoComo en el cicloAux <- c.array[2*i+1]
                         c.array[2*i+1] <- c.array[i]
                         c.array[i] <- elementoAux
                         i <- 2*i+2
                    }
                    else {
                    //Sino es ninguno de los dos casos anteriores, entonces termine porque no puedo 
                    //intercambiar mas valores. 
                         noTermine <-false
                    }
               }
               //Si solo tiene el hijo izquierdo definido, entonces me fijo si lo reemplazo
               else if (soloEstaDefinidoElHijoIzq) {
                    if (c.array[2*i+1] < c.array[i]) {
                         elementoAux <- c.array[2*i+1]
                         c.array[2*i+1] <- c.array[i]
                         c.array[i] <- elementoAux
                         i <- 2*i+1
                    }
               //Sino tiene ninguno de los hijos definidos, entonces es una hoja
               else {
                    noTermine <-false

               }
          }
	}
	\end{verbatim}
\hspace*{1em} \textcolor{red}{----------------------------------------} \\
\hspace*{1em} i$\#$ (in c :conjAcotado($\alpha$))$\longrightarrow$ res : nat
	\begin{verbatim}
	{
        if (c.ultimaPosUsada = 0) {
                 res = 0
        }
        else {
                 res = c.ultimaPosUsada -1
        }
	}
	\end{verbatim} 
\hspace*{1em} \textcolor{red}{----------------------------------------} \\
\hspace*{1em} i$<$- (in c :conjAcotado($\alpha$))$\longrightarrow$ res : conjAcotado($\alpha$)
	\begin{verbatim}
	{
        var
                indice : nat
        indice <-0
        res.ultimaPosUsada <- c.ultimaPosUsada
        while (indice < tam(res.array)) {
                if (definido?(c.array, indice)) {
                        res.array[indice] <- c.array[indice]
                }
                indice++
        }
	}
	\end{verbatim} 
\hspace*{1em} \textcolor{red}{----------------------------------------} \\
\hspace*{1em} i$\bigcup$ (in c1 :conjAcotado($\alpha$), in c2: conjAcotado($\alpha$))$\longrightarrow$ res : conjAcotado($\alpha$)
	\begin{verbatim}
	{
        var
                indice : nat
	
        res.array <- crearArreglo(long(c2.array) + long(c1.array))
        res.ultimaPosUsada <- 0
        indice <- 0
        //primero tengo que llenar a res tal que sus valores me den falso cuando pregunto por el definido
        while (indice < long(c2.array) + long(c1.array)) {        
                res.array[indice] <- nil
                indice++
        }
        //primero copio el primer conjunto directamente porque se que cumple el invariante
        while (indice < c1.ultimaPosUsada) {
                if (definido?(c1.array, indice)) {
                        res.array[indice] <- c1.array[indice]
                        res.ultimaPosUsada++
                }
                indice++
        }
        indice <- 0
        //ahora agrego los elementos del segundo conjunto
        //como no los puedo agregar directamente, uso la funcion Ag()
        while (indice < c2.ultimaPosUsada) {
                if (definido?(c1.array, indice)) {
                        Ag( c2.array[indice], res)
                }
                indice++
        }
        return res
	}
	\end{verbatim} 
\newpage
\normalfont
\justificaord
\justord{\emptyset}{La funcion tiene orden O(n) porque crear el arreglo de dimension tamanio tiene orden O(1), y lo mismo con inicializar un nat. Sim embargo, el hecho de llenar el arreglo con posiciones no definidas toma O(n)}
\justord{Ag}{Las primeras asignaciones tienen orden O(1). En el peor de los casos, empeze desde la ultima posicion del arreglo y subo hasta la primera, y como subo siempre de a ''mitades`` de lo que me falta esto me tomaria log n pasos, siendo n la longitud del arreglo. Como todas las operaciones que figuran dentro del ciclo tienen orden O(1) por que se trabaja sobre un arreglo dimensionable o sobre un nat, el mismo va a tener orden O(log n).  Por lo tanto, como las operaciones antes del ciclo tienen orden O(1) y el ciclo O(log n), la funcion termina teniendo orden O(log n)}
\justord{\in}{Esta funcion tiene que chequear elemento a elemento si esta en el conjunto o no como el conjunto esta implementado sobre una arreglo seria lo mismo que preguntar si el elemento esta en el arreglo, por lo que la funcion tiene orden O(n) siendo n = \#(c)}
\justord{\emptyset?}{Como para ver si el conjunto esta vacio, me fijo en el valor de una variable de tipo Nat, esto es O(1)}
\justord{dameUno}{Esta funcion devuelve el primero del arreglo, por lo que el orden es O(1)}
\justord{sinUno}{Las operaciones antes de empezar el ciclo tiene orden O(1). La guarda del ciclo tiene orden O(1). En el ciclo empiezo desde la primer posicion y voy hasta la ultima, como como voy avanzado de a mitades, esto tomaria 0(log n) siendo n = tam(c.array).  Como todas las operaciones que estan dentro del ciclo tienen orden O(1), todo el ciclo tiene orden O(log n). Como las operaciones fuera del ciclo tienen orden O(1) porque son asignaciones u operaciones sobre nat y bool, toda la funcion tiene orden O(log n)}
\justord{\#}{Como la comparacion en el IF tiene orden O(1), y las dos asignaciones tambien, el orden de esta funcion es O(1)}
\justord{<-}{Las asignaciones del antes del ciclo son O(1) porque son sobre nat. La guarda del ciclo tiene orden O(1). Como el while lo hago desde la posicion 0 hasta el n-1, entonces tiene orden O(n) siendo n la longitud del arreglo. Como las posiciones dentro del mismo tienen orden O(1), toda la funcion va a tener orden O(n)}
\justord{\bigcup}{El primer while tiene orden O(k + j), siendo k y j la longitudes de los arreglos de cada uno de los conjuntos. En el segundo estoy copiando todos los datos del conjunto c_1 a res, por lo que tiene O (c_1.ultimaPosUsada). En el segundo while, agrego todos los valores del conjunto c_2 a res, pero usando la funcion Ag(), por lo que va a tener orden O(c_2.ultimaPosUsada * log(k +j)), ya que hago c_2.ultimaPosUsada, y el Ag tiene orden O(log(k+j)).  }

\end{dis}



